Construction of polar codes for arbitrary discrete memoryless channels

摘要

It is known that polar codes can be efficiently constructed for binary-inputchannels. At the same time, existing algorithms for general input alphabets areless practical because of high complexity. We address the construction problemfor the general case, and analyze an algorithm that is based on successivereduction of the output alphabet size of the subchannels in each recursionstep. For this procedure we estimate the approximation error as$O(\mu^{-1/(q-1)}),$ where $\mu$ is the "quantization parameter," i.e., themaximum size of the subchannel output alphabet allowed by the algorithm. Thecomplexity of the code construction scales as $O(N\mu^4),$ where $N$ is thelength of the code. We also show that if the polarizing operation relies on modulo-$q$ addition,it is possible to merge subsets of output symbols without any loss insubchannel capacity. Performing this procedure before each approximation stepresults in a further speed-up of the code construction, and the resulting codeshave smaller gap to capacity. We show that a similar acceleration can beattained for polar codes over finite field alphabets. Experimentation shows that the suggested construction algorithms can be usedto construct long polar codes for alphabets of size $q=16$ and more withacceptable loss of the code rate for a variety of polarizing transforms.